package paper.graph;

//import java.lang.Clonable;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.Iterator;
import java.io.PrintWriter;
import paper.db.Paper;
import paper.db.PaperIndex;


public class PaperGraph<T extends Edge,
                        V extends Vertex>
{
    // Fix some of the flaws in generics by enforcing a default
    // and a copy constructor for all generic Edge types.
/*public interface EdgeBuilder<T>
{
    T makeDefault(String a, String b);
    T copy();
}*/
    /*class Edge
    {
        String keyA, keyB; // Implied in lookup but for convenience...
        int number;
        int colour;

        Edge(String a, String b)
        {
            keyA = a;
            keyB = b;
            number = -1;
            colour = -1;
        }
    }*/

    PaperIndex index;
    HashMap<String,HashMap<String,T>> lookup;
    HashSet<T> edges;
    public HashMap<String,V> vertices;

    /* To support synthetic graphs the PaperIndex can be null.
       In which case no lookups are done and the keys are used
       as node names when generating output.
    */
    public PaperGraph( PaperIndex pc )
    {
        index = pc;
        lookup = new HashMap<String,HashMap<String,T>>();
        edges = new HashSet<T>();
        vertices = new HashMap<String,V>();
    }

    /* This needs to be a proper deep copy, not just of the mappings
       that describe the grpah, but also the underlying stored data.
    */
    public PaperGraph( PaperGraph<T,V> copy )
    {
        index = copy.index; // Singleton, so just take ref
        lookup = new HashMap<String,HashMap<String,T>>();
        for( String s : copy.lookup.keySet() )
            lookup.put( s, deepInner( copy.lookup.get(s) ));
        // No point storing references to T objects in the
        // copy as we've just cloned new ones. Dig all of
        // the new cloned Ts out of lookup.
        edges = new HashSet<T>();
        vertices = new HashMap<String,V>();
        for( String oKey : lookup.keySet() )
        {
            HashMap<String,T> inner = lookup.get(oKey);
            for( T t : inner.values() ) {
                edges.add( t );
                if( vertices.get(t.keyA)==null)
                    vertices.put( t.keyA, (V)copy.vertices.get( t.keyA ).copy() );
                if( vertices.get(t.keyB)==null)
                    vertices.put( t.keyB, (V)copy.vertices.get( t.keyB ).copy() );
            }
        }
    }

    HashMap<String,T> deepInner( HashMap<String,T> in )
    {
        HashMap<String,T> cloneSet = new HashMap<String,T>();
        for( String s : in.keySet() )
        {
            T old = in.get(s);
            T copy = (T)old.copy();  // All custom edges must override
            cloneSet.put( s,copy ); 
        }
        return cloneSet;
    }

    HashMap<String,T> makeInner( String key )
    {
        HashMap<String,T> es = lookup.get(key);
        if( es==null )
        {
            es = new HashMap<String,T>();
            lookup.put( key, es );
        }
        return es;
    }

    public Set<T> edgeSet()
    {
        return edges;
    }

    public void removeEdge(String keyA, String keyB)
    {
        HashMap<String,T> x = lookup.get(keyA);
        if( x!=null )
        {
            if( x.size()==1 )
            {
                Set<String> set = lookup.keySet();
                set.remove(keyA);
            }
            else
            {
                Set<String> set = x.keySet();
                set.remove(keyB);
            }
        }
        x = lookup.get(keyB);
        if( x!= null )
        {
            if( x.size()==1 )
            {
                Set<String> set = lookup.keySet();
                set.remove(keyB);
            }
            else
            {
                Set<String> set = x.keySet();
                set.remove(keyA);
            }
        }
    }

    public void addEdge(String keyA, String keyB, T e)
    {
        if(!containEdge(keyA,keyB))
        {
            HashMap<String,T> esA = makeInner(keyA);
            HashMap<String,T> esB = makeInner(keyB);
            esA.put(keyB,e);
            //System.out.println(keyA + " " + keyB + " " + esA.keySet().size());
            esB.put(keyA,e);
            edges.add(e);
            if( vertices.get(keyA) == null )
                vertices.put(keyA, (V)V.makeDefault(keyA) ); 
            if( vertices.get(keyB) == null )
                vertices.put(keyB, (V)V.makeDefault(keyB) ); 
        }
    }

    /* The bug with data disappearing from the graph is because the
       Set returned is a view of the actual Map. Any changes are 
       reflected. If this is not desired (eg for destructive updates)
       then clone the Set before use.
    */
    public Set<String> getNeighbours(String key)
    {
        HashMap<String,T> x = lookup.get(key);
        if( x==null )
            return new HashSet<String>();
        return x.keySet();
    }

    // We don't have to check the order of keyA|keyB or 
    // keyB|keyA because addEdge always builds both
    // paths (the underlying matrix is symmetric).
    boolean containEdge(String keyA, String keyB)
    {
        HashMap<String,T> inner = lookup.get(keyA);
        if(inner==null)
            return false;
        T edge = inner.get(keyB);
        return (edge==null) ? false : true;
    }
    



    // Start at the node with key pk and use breadth-first search
    // to perform a controlled flood-fill of the given depth. After
    // the fill, all nodes with the depth bound of the start node
    // are loaded into the PaperGraph and all edges between loaded
    // nodes are populated in edges. The HashSet of edges
    // for each node is partial as it does not contain links to 
    // other regions on the graph.
    public void fillGraph( String pk, int depth, String edgeType, T def)
    {
        HashSet<String> nextWork,workList = new HashSet<String>();
        workList.add( pk );
        HashSet<String> done = new HashSet<String>();

        for( int i=0; i<depth+1; i++) {
            nextWork = new HashSet<String>();
            //System.out.println("Depth " + depth + ", " + workList.size());
            for(String wKey : workList )
            {
                HashSet<String> cited = Paper.getEdges( wKey, edgeType );
                nextWork.addAll( cited );
                for(String nKey : cited )
                    addEdge( wKey, nKey, (T)def.makeDefault(wKey,nKey) ); // See warning at top of Edge class
            }
            done.addAll( workList );
            nextWork.removeAll( done );
            workList = nextWork;
            //System.out.println("Step " + i + " workList " + workList.size() );
        }
        //clampEdges(); What did this do?
    }

    // Using the key pk as a starting point fill the graph with
    // citation and reference links. The resulting combination of
    // the two digraphs is an undirected graph.
    public void fillCiteGraphs( String pk, T defEdge, int depth )
    {
        HashSet<String> workList = new HashSet<String>();
        HashSet<String> doneList = new HashSet<String>();
        HashSet<String> nextList;
        workList.add( pk );

        while( depth-- > 0 && workList.size()>0 )
        {
            nextList = new HashSet<String>();
            System.out.println("Depth " + depth + " " + workList.size() + " " + doneList.size() );
            for( String key : workList ) 
            {
                System.out.println("Working " + key  + " " +
                        workList.size() + "/" + doneList.size());
                HashSet<String> set = Paper.getEdges( key, "citations");
                for( String tKey : set ) {
                    T newEdge = (T)defEdge.makeDefault(key,tKey);
                    addEdge( key, tKey, newEdge );
                    if( !doneList.contains(tKey) && !workList.contains(tKey))
                        nextList.add(tKey);
                }
                set = Paper.getEdges( key, "references");
                for( String tKey : set ) {
                    T newEdge = (T)defEdge.makeDefault(key,tKey);
                    addEdge( key, tKey, newEdge );
                    if( !doneList.contains(tKey) && !workList.contains(tKey))
                        nextList.add(tKey);
                }
                doneList.add( key );
            }
            workList = nextList;
        }
    }

    /*void clampEdges()
    {
        Set<String> nodes = edges.keySet();
        for( Iterator<String> ns=nodes.iterator(); ns.hasNext(); ) {
            HashSet<String> cites = edges.get( ns.next() );
            cites.retainAll( nodes );
        }
    }*/

    public void dump()
    {
        for( String key : lookup.keySet() )
        {
            System.out.println("Key: " + key);
            HashMap<String,T> cites = lookup.get(key);
            for( String eKey : cites.keySet() )
                System.out.println("Edge: " + eKey + " = " +
                                   cites.get(eKey) );
        }
    }

    public void dot(PrintWriter out, boolean fluff, boolean directed)
    {
        String arrow = directed ? "->" : "--";
        if( fluff && directed)
            out.println("digraph {");
        if( fluff && !directed)
            out.println("graph {");
        if( !directed )
            out.println(" graph [overlap=scale];");
        for( V v : vertices.values() )
        {
            Paper p;
            String nodeName;
            if( index!=null && (p=index.findKey(v.key))!=null )
                nodeName = p.flatTitle;
            else
                nodeName = "key" + v.key;
            //System.out.println("Edges from " + key);
            out.println("key" + v.key + " [" + v.toString(index) + ",fontcolor=white];");
        }
        for( String key : lookup.keySet() )
        {
            //System.out.println("Dotting " + key);
            HashMap<String,T> cites = lookup.get(key);
            for( String other : cites.keySet() )
            {
                //System.out.println("Inside " + other);
                if( key.compareTo( other ) > 0 ) {
                    String edgeAts = cites.get(other).toString();
                    out.println("key" + key + " " + arrow + " key" + 
                                other + " " + edgeAts + ";");
                }
                //else
                //    System.out.println("Cmp " + key.compareTo(other));
            }
        }
        if( fluff )
            out.println("}");
    }
}
